package com.solution.preprocessing;

import java.util.Deque;
import java.util.LinkedList;

/*
    括号预处理（Parenthesis Preprocessing）
 */
public class Solution {

    /*
    在法一的Stack解题方法中，不足之处在于使用reverse()，该函数的时间消耗非常巨大, 对于每一对符号我们都要反转其括号内的字符，使得时间复杂度提升到O(n^2)。
    我们发现其实我们并不需要真的去反转字符，只需要得到一个顺序正确的字符串返回即可，因此我们可以对括号进行预处理，交换其左右括号的坐标。因此我们在向右遍历到左括号时实则跳到了右括号向左遍历。
     */
    public String reverseParentheses(String s) {
        int len = s.length();
        int[] pair = new int[len];
        Deque<Integer> stk = new LinkedList<>();
        for ( int i = 0 ; i < len ; i++ ) {
            if ( s.charAt(i) == '(' ) {
                stk.push(i);
            } else if ( s.charAt(i) == ')' ) {
                int position = stk.pop();  // 当前右括号对应的左括号的所在的下标
                pair[i] = position;  // 当前右括号位置上，存储"左括号的下标"
                pair[position] = i;  // 同理，左括号的位置上，存储"右括号的下标"
            }
            // 不处理字母等非括号字符
        }

        StringBuffer str = new StringBuffer();
        int index = 0, step = 1;
        while ( index < len ) {
            if ( s.charAt(index) == '(' || s.charAt(index) == ')' ) {
                index = pair[index];  // （遇到括号时，）切换到与之相反的括号上
                step = -step;  // 转变指针方向
            } else {
                str.append(s.charAt(index));
            }
            index += step;
        }
        return str.toString();
    }

}
/*
复杂度分析

时间复杂度：O(n)，其中 n 为字符串的长度。预处理出括号的对应关系的序列的时间复杂度为 O(n)，遍历字符串的时间复杂度同样为 O(n)。

空间复杂度：O(n)，其中 n 为字符串的长度。栈的大小不会超过 n，以及我们需要 O(n) 的空间记录括号的对应关系。
 */